#include <vector>
#include <iostream>

using namespace std;

// 并归算法
void split(vector<int> &input, int left, int right);

void merge(vector<int> &input, int left, int mid, int right);

void sort(vector<int> &input) {
    int len = input.size();
    split(input, 0, len - 1);
}

void split(vector<int> &input, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        split(input, left, mid);
        split(input, mid + 1, right);
        merge(input, left, mid, right);
    }
}

void merge(vector<int> &input, int left, int mid, int right) {
    int i = left;
    int j = mid + 1;

    vector<int> tmp = {};

    while (i <= mid && j <= right) {
        if (input[i] <= input[j]) {
            // tmp[t++] = input[i++]; 注意：这样写会报错
            tmp.push_back(input[i++]);
        } else {
            tmp.push_back(input[j++]);
            // tmp[t++] = input[j++];
        }
    }

    while (i <= mid) {
        tmp.push_back(input[i++]);
    }

    while (j <= right) {
        tmp.push_back(input[j++]);
    }

    int t = 0;
    while (left <= right) {
        input[left++] = tmp[t++];
    }
}

int main() {
    vector<int> a = {3, 1, 2, 4, 7, 1, 8, 5, 2, 9};
    sort(a);
    for (auto i : a) {
        cout << i << ",";
    }
    cout << endl;

    return 0;
}